package leetcode_401_500;

import java.util.Arrays;

public class LeeCode_433 {
    public static void main(String[] args) {
//        System.out.println(minMutation("AACCGGTT", "AACCGGTA", new String[]{"AACCGGTA"}));
        System.out.println(minMutation("AAAAAAAA", "CCCCCCCC",
                new String[]{"AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC",
                        "AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCA"}));
    }
    private static int minMutation(String startGene, String endGene, String[] bank) {
        int n = bank.length;
        int[][] dp = new int[n][n];
        int endI = -1;
        for (int i = 0; i < n; i++) {
            if (bank[i].equals(endGene)){
                endI = i;
            }
            Arrays.fill(dp[i], 1000);
        }
        if (endI == -1)
            return -1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (charge(bank[i], bank[j])){
                    dp[i][j] = 1;
                    dp[j][i] = 1;
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
                }
            }
        }
        int ans = 1000;
        for (int i = 0; i < n; i++) {
            String s = bank[i];
            if (charge(s, startGene)){
                ans = Math.min(ans, dp[i][endI] + 1);
            }
        }
        return ans == 1000 ? -1 : ans;
    }

    private static boolean charge(String s1, String s2) {
        int c = 0;
        for (int k = 0; k < s1.length(); k++) {
            if (s1.charAt(k) != s2.charAt(k)){
                c++;
            }
            if (c >= 2)
                return false;
        }
        return c == 1;
    }
}
